#include <iostream>
#include <cstdio>
#include <cassert>
#include <algorithm>


using namespace std;


void PrintArray(int* array, int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << array[i] << " ";
    }

    cout << endl;
}

// //堆的向下调整算法
// void adjustDown(int* a, int n, int root)
// {
// 	int parent = root;
// 	int child = 2 * parent + 1;//假设左孩子较大

// 	while (child < n)
// 	{
// 		if (child + 1 < n && a[child + 1] > a[child])//右孩子存在，并且比左孩子大
// 		{
// 			child++;//左右孩子的较大值
// 		}
// 		if (a[child] > a[parent])
// 		{
// 			swap(a[child], a[parent]);
// 			parent = child;
// 			child = 2 * parent + 1;
// 		}
// 		else//已成堆
// 		{
// 			break;
// 		}
// 	}
// }



// void adjustDown(int* array, int n, int root)
// {
//     int parent = root;
//     int child = parent * 2 + 1;

//     while(child < n)
//     {
//         // 找小？

//         if(child + 1 < n && array[child + 1] < array[child])
//         {
//             child++;
//         }

//         if(array[parent] < array[child])
//         {
//             std::swap(array[parent], array[child]);
//             parent = child;
//             child = parent * 2 + 1;
//         }
//         else
//         {
//             break;
//         }

//     }
// }

// void SortArray(int* array, int n)
// {
//     // 先建堆 - 排升序 - 建大堆
//     for(int i = (n - 1 - 1) / 2; i >= 0; i--)
//     {
//         adjustDown(array, n, i); 
//     }
//     // 第一个for循环建堆完成后能保证的是堆顶数据是最大值

//     // 记录堆中最后一个数据的下标
//     int end = n - 1;

//     while(end > 0)
//     {
//         std::swap(array[0], array[end]);
//         adjustDown(array, end, 0); // 最大的数不参与调整
//         end--;
//     }
// }


// // 堆的向下调整算法
// void AdjustDown(int* array, int n, int parent)
// {
//     int child = parent * 2 + 1; // 默认是左孩子大

//     while(child < n)
//     {
//         if(child + 1 < n && array[child + 1] > array[child])
//         {
//             child++;
//         }

//         if(array[child] > array[parent])
//         {
//             swap(array[child], array[parent]);
//             parent = child;
//             child = parent * 2 + 1;
//         }
//         else
//         {
//             break;
//         }
//     }
// }

// void HeapSort(int* array, int n)
// {
//     // 先建堆 - 排升序 - 建大堆
//     for(int i = (n - 1 - 1) / 2; i >= 0; i--)
//     {
//         AdjustDown(array, n, i);
//     }

//     // 第一个for循环结束之后，堆顶数据是最大值

//     int end = n - 1;

//     while(end)
//     {
//         swap(array[0], array[end]);
//         AdjustDown(array, end, 0);
//         end--;
//     }
// }


// 堆的向下调整
void AdjustDown(int* array, int n, int parent)
{
    int child = parent * 2 + 1;

    while(child < n)
    {
        if(child + 1 < n && array[child + 1] > array[child])
        {
            child++;
        }

        if(array[child] > array[parent])
        {
            swap(array[child], array[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}


void HeapSort(int* array, int n)
{
    // 先建堆 - 排升序 - 建大堆
    // 从最后一个非叶子节点开始向下调整 - 因为叶子节点本身就可视为小堆或者大堆
    for(int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(array, n, i);
    }

    // 第一个for循环结束之后，堆顶数据是最大值

    int end = n - 1;

    while(end)
    {
        swap(array[0], array[end]);
        AdjustDown(array, end, 0);
        end--;
    }
}

int main()
{
    int array[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    PrintArray(array, 10);

    HeapSort(array, 10);

    PrintArray(array, 10);

    return 0;
}



void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if(begin >= end)
        return;

    int mid = begin + (end - begin) / 2;

    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);

    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int index = begin;

    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] < a[begin2])
            tmp[index++] = a[begin1++];
        else    
            tmp[index++] = a[begin2++];
    }

    while(begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }

    while(begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }

    memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}


void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    assert(tmp);

    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}



int main()
{
    int array[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    PrintArray(array, 10);

    MergeSort(array, 10);

    PrintArray(array, 10);

    return 0;
}

void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;

    while(child < n)
    {
        if(child + 1 < n && a[child + 1] > a[child])
            child++;

        if(a[child] > a[parent])
        {
            std::swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}


void HeapSort(int* a, int n)
{
    for(int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    int end = n - 1;

    while(end)
    {
        std::swap(a[0], a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}




void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if(begin >= end)
    {
        return;
    }

    int mid = begin + (end - begin) / 2;

    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);

    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int index = begin;

    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] < a[begin2])
            tmp[index++] = a[begin1++];
        else
            tmp[index++] = a[begin2++];
    }

    while(begin1 <= end1)
        tmp[index++] = a[begin1++];
    while(begin2 <= end2)
        tmp[index++] = a[begin2++];

    memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}


void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    assert(tmp);

    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}



